# -*- coding: utf-8 -*-
import random

__author__ = 'raniys'


# 序列是由1-100000的连续数字组成
def find_value_in_sequence_list():
    # 生成数列，一万个数
    arr_length = 100001
    list = range(1, arr_length)

    # 插入一个随机数
    rnd = random.randrange(1, arr_length)
    list.insert(rnd - 1, rnd)

    print '\n重复数为：' + str(rnd)
    print'\n开始查找'

    # 正式开始查找算法
    left = 0
    right = arr_length
    count = 0

    while (right - left) > 1:
        pos = (left + right) / 2
        count = count + 1
        print '第 %d 次定位：%d' % (count, pos)
        if list[pos] == pos:
            right = pos
        else:
            left = pos

    print '\n查找结果：', list[left]


def find_without_sequence_list():
    # 生成数列
    arr_length = 10001
    list = range(1, arr_length)

    # 加入一个随机数
    rnd = random.randrange(1, arr_length)
    list.append(rnd)
    print '\n重复数为：' + str(rnd)

    # 打乱顺序
    random.shuffle(list)

    # 正式开始查找算法
    count = 0
    idx = 0
    while list[idx] != 0:
        count = count + 1
        temp = list[idx]
        list[idx] = 0
        idx = temp

    print "找到：%d，循环 %d 次" % (temp, count)


find_without_sequence_list()
